This invention relates to the detection and correction of skew and shift in images scanned into a system by an optical line scanning device.
The use of optical line scanners to enter an image into a system such as a facsimile machine or copy machine as well as a character recognition machine is well established. In some systems, the document to be entered is placed on a flat surface and is either scanned in place by optical and mechanical means or is fed through the machine by rollers. In all of these systems, there is the probability that the document will by placed or fed through the machine at an offset position and/or a skew angle. The result is that pages of copy or facsimile come out of the system looking tilted, which may make them distracting to read by a person or difficult to read by a computer or other mechanized analysis.
Rundle, U.S. Pat. No. 3,831,146 teaches pre-scanning hand written characters which are often written at a slant to the right from the vertical. The pre-scan uses scan lines at 60, 70 and 90 degrees from the horizontal. Each time that a character is scanned, special combinatorial logic operates on the stored character and develops a count of the number of predominant line segments found at that angle. The angle having the greatest number of predominant line segments is chosen as the recognition scan angle. This system does not work for images that do not have a significant number of vertical line components in the character set or for other images of non text documents.
Chevillat, U.S. Pat. No. 4,338,588 teaches a mechanical method for rotating, relative to a document, optical transducer apparatus having a plurality of parallel elongated light transducers. Signals accumulated from the transducers reach a distinct maximum when the transducers have been rotated so that the elongation of the transducers are in line with the printed lines on the document. This has the shortcomings of mechanical systems which include wear, unreliability, and low speeds.
Schlang, U.S. Pat. No. 4,558,461 teaches the formation of logical swaths vertically through image data and creates a list of data intersections with the swaths. Using these intersections, blocks of text are detected. All points in a block are set to black and then used to distinguish lines from which skew angles are derived by the method of linear regression.
The Schlang method is complex and manipulates the data after it has been stored in memory which adds to system costs and processing time.
Postl, U.S. Pat. No. 4,723,297 teaches the use of a sequence of systematically selected search angles which are either simulated or calculated using Fourier analysis. A critical precondition for successful operation with the Postl method is a significant content of horizontal or vertical members in the text source material on the document, which means that non-text images are not acceptable.
Baird, U.S. Pat. No. 5,001,766 discloses a method which locates characters by finding the lower right point of the character and then running "bin counts" at a series of skew angles by adding up the dots for each angle. The largest value determines the angle of document orientation or skew. The skew angles are imaginary lines onto which the image is projected by mechanically rotating the projection device. Further, the use of the lower right point of a character depends on a bottom or down reference which must be predefined.
The document is then mechanically reoriented to correct the skew. The use of mechanical projection adversely affects reliability and the creation of the down reference is a time consuming manual step.
Kita, U.S. Pat. No. 5,027,227 rotates blocks or subsections of images in parallel and then relies on manual operator input to determine skew angle. Blocks of image are then moved which can result in disjointed lines being produced by the rotation.
Lee, U.S. Pat. No. 5,054,098 teaches the creation of polygons by tracing the contour of individual objects which have been detected by horizontal scans. Large polygons are then created and selected to determine line angle. A modified Hough transform is used to detect straight lines from which the skew angle is detected. The skew is then corrected by matrix operation.
These methods are time consuming and require extensive computation overhead.
Ikehira U.S. Pat. No. 5,093,653 teaches a manual method where the operator selects a point and then visually creates a reference line from which the system calculates the skew angle and rotates the image.
Itoh U.S. Pat. No. 5,050,225 describes a method for rotating an existing bit map though various angles using shear rotation. The skew angle is not detected but is assumed to be already known.